#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<vector<int>> pre;
    int m,n;
    int dx[2]={0,1};
    int dy[2]={1,0};
    int dfs(int x,int y)
    {
        if(x==m-1&&y==n-1) return 1;
        if(pre[x][y]!=-1) return pre[x][y];
        int ret=0;
        for(int i=0;i<2;i++)
        {
            int cx=x+dx[i];
            int cy=y+dy[i];
            if(cx>=0&&cx<m&&cy>=0&&cy<n)
            {
                ret+=dfs(cx,cy);
            }
        }
        pre[x][y]=ret;
        return ret;
    }
    int uniquePaths(int m_, int n_) 
    {
        m=m_;n=n_;
        pre=vector<vector<int>>(m,vector<int>(n,-1));
        return dfs(0,0); 
    }
};